МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
з лабораторної роботи №3
з дисципліни
“ Теорія алгоритмів і математичні основи
представлення знань ”
на тему:
Емуляція на ПЕОМ машин Тюрінга
Львів-2007
Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тюрінга і констроювання програм для них.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Для засвоєння поняття машин Тюрінга і освоєння конструювання Т-машин (єх програм) необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм).
Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тюрінга, якаб по заданій Т-програмі Пт і входу w імітувала обчислення функціє F, що задається Пт.
В основі алгоритмічноє системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієє машини.
I. Нехай задано вхідний алфавіт Eвх = {a1,..,an},внутрішній алфавіт Eвн = {b1,..,br},і E є об"єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами.
Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів.
Довільну скінченну підмножину Q = {q0,q1,..,qm} деякої нескінченноє множини Q^ = {..,q(-1),q0,..qm,..} будемо називати множиною міток, а єє елементи - мітками.
Будемо вважати, що перетин Q і E є пустою множиною.
Командю Тюрінга (Т-командою ) називається вираз вигляду
q d -> q'd'r (1)
де q і q' - мітки із Q, d і d' - літери із E, а r приймає значення одного із трьох чисел : -1,0,+1. Пара qd із (1) називається Т-міткю. Програмою Тюрінга (Т-прграмою) називається двільна скінченна сукупність Пт Т-команд
U0
U1 (2)
..
Um
в якій різні команди мають різні Т-мітки остання умова означає, що кожна Т-команда
Ui = ( qi di -> qi'di'ri ) (3)
в Пт однзначно визначається по своєй Т-мітці.
Машиною Тюрінга називається довільний набір Мт = (Q,E,q^,#,Пт), --------------- ---------------
де:
Q - множина міток;
E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів;
q^ - виділений елемент із Q, який називається початковою міткою Мт;
# - виділений елемент із Eвн;
Пт - Т-програма.
Коли кманда q d -> q'd'r входить в програму Пт Т-машини Мт, тді мітка q і Т-мітка (q d) називаються прміжковими мітками йієє машини. Всі непромщжкві мітки і Т-мітки називаються кінцевими мітками Т-машини Мт.
Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність
t = ...d(-2) d(-1) q d(0) d(1) d(2)... (4)
де d(j) (j = ...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q.
Для машини Мт Т-стан (4) називається : а) початковим, коли q = q^
б) проміжковим, коли < q d(0) > - проміжкова Т-мітка; в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт.
Множину всіх станів Т-машини Мт позначимо через Dм.
Тепер визначимо функцію переходів Fт : Dм --> Dм.
Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t) = t.
Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> --> q'd'r. Під дією цієї команди Т-стан t переходить в стан t' = Fт(t). Залежно від r = +1,0,-1 значення tr = Fт(t) приймє вигляд :
t+ = ...d(-2) d(-1) d' q' d(1) d(2)...
t0 = ...d(-2) d(-1) q' d' d(1) d(2)... (5)
t- = ...d(-2) q' d(-1) d' d(1) d(2)...
Із (5) випливає,що при r = +1,0,-1 вираз "q d(0)" в стані(4), відповідно,замінюється на вир...
